/*
地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，
它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。
例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

 

示例 1：

输入：m = 2, n = 3, k = 1
输出：3
示例 2：

输入：m = 3, n = 1, k = 0
输出：1
提示：

1 <= n,m <= 100
0 <= k <= 20

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

#include "../stdc++.h"

// bfs
class Solution {
public:
    int getSum(int x) {
        int res{0};
        while (x) {
            res += x % 10;
            x /= 10;
        }
        return res;
    }
    int movingCount(int m, int n, int k) {
        if (k == 0) return 1;
        queue<pair<int, int>> q{};
        vector<vector<int>> dirs{{0, 1}, {1, 0}}; // 向右或向下
        vector<vector<int>> visited(m, vector<int>(n, 0));
        q.push(make_pair(0, 0));
        visited[0][0] = 1;
        int res{1};
        while (!q.empty()) {
            auto p = q.front();
            int x = p.first;
            int y = p.second;
            q.pop();
            for (auto dir : dirs) {
                int newx = x + dir[0];
                int newy = y + dir[1];
                if (newx < 0 || newx >= m || newy < 0 || newy >= n || visited[newx][newy] == 1 || getSum(newx) + getSum(newy) > k) {
                    continue;
                }
                q.push(make_pair(newx, newy));
                visited[newx][newy] = 1;
                ++res;
            }
        }
        return res;
    }
};

// 递推
class Solution {
public:
    int getSum(int x) {
        int res{0};
        while (x) {
            res += x % 10;
            x /= 10;
        }
        return res;
    }
    int movingCount(int m, int n, int k) {
        if (k == 0) return 1;
        vector<vector<int>> visited(m, vector<int>(n, 0));
        int res{1};
        visited[0][0] = 1;
        for (int i{0}; i < m; ++i) {
            for (int j{0}; j < n; ++j) {
                if ((i == 0 && j == 0) || getSum(i) + getSum(j) > k) {
                    continue;
                }
                if (i >= 1) {
                    visited[i][j] |= visited[i - 1][j];
                }
                if (j >= 1) {
                    visited[i][j] |= visited[i][j - 1];
                }
                res += visited[i][j];
            }
        }
        return res;
    }
};